package q69_mySqrt;

public class Solution_1 {
    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        System.out.println(s.mySqrt(2147395599));
    }

    /**
     * 用二分法可以很简单的解决这道问题，但是需要注意是，题目中x的范围设置达到了Integer的最大值
     * 所以在中途相乘的时候有可能溢出，也就会导致出现问题，因此需要设置long
     */
    public int mySqrt(int x) {

        long l = 0, r = x;
        while (r - l > 1) {
            if (((l + r) / 2) * ((l + r) / 2) > x) {
                r = (int)(l + r) / 2;
            } else {
                l = (int)(l + r) / 2;
            }

        }
        return (int)(r * r <= x ? r : l);
    }
}
